//如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数
//值排序之后中间两个数的平均值。
//
// 例如，
//
// [2,3,4] 的中位数是 3
//
// [2,3] 的中位数是 (2 + 3) / 2 = 2.5
//
// 设计一个支持以下两种操作的数据结构：
//
//
// void addNum(int num) - 从数据流中添加一个整数到数据结构中。
// double findMedian() - 返回目前所有元素的中位数。
//
//
// 示例 1：
//
// 输入：
//["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
//[[],[1],[2],[],[3],[]]
//输出：[null,null,null,1.50000,null,2.00000]
//
//
// 示例 2：
//
// 输入：
//["MedianFinder","addNum","findMedian","addNum","findMedian"]
//[[],[2],[],[3],[]]
//输出：[null,null,2.00000,null,2.50000]
//
//
//
// 限制：
//
//
// 最多会对 addNum、findMedian 进行 50000 次调用。
//
//
// 注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-
//stream/
//
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 446 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 这个解法很慢
class MedianFinder {
    num : number[]
    constructor() {
        this.num = []
    }
    addNum(num: number): void {
        this.num.push(num)
    }

    findMedian(): number {
        this.num.sort((a,b) => a - b)
        return this.num.length % 2 === 1 ? this.num[Math.floor(this.num.length / 2)] : (this.num[this.num.length / 2] + this.num[this.num.length / 2 - 1]) / 2
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */
//leetcode submit region end(Prohibit modification and deletion)
// ? 每次都是二分法寻找插入位置 快一些
class MedianFinder2 {
    nums : number[]
    constructor() {
        this.nums = []
    }

    addNum(num: number): void {
        let len = this.nums.length
        let left = 0;
        let right = len - 1;
        while (left <= right) {
            let mid = left + right >> 1;
            if (this.nums[mid] === num) {
                //? 在mid处添加元素，后面的元素会往后移动的
                this.nums.splice(mid, 0, num);
                return;
            }
            else if (this.nums[mid] < num) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        //? 在right + 1处添加元素，后面的元素没有元素了
        this.nums.splice(right + 1, 0, num);
    }

    findMedian(): number {
        let len = this.nums.length
        let m = len >> 1
        if(len%2 === 0){
            return (this.nums[m] + this.nums[m-1])/2
        }
        else {
            return this.nums[m]
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */
